package _0000_study._leetcode._interview._17_14_smallestK;

import java.util.Arrays;
import java.util.stream.Collectors;

/**
 * Date: 2020/12/5 15:29
 * Content: 使用快排中的partition解决
 * <p>
 * 执行用时：3 ms, 在所有 Java 提交中击败了83.89%的用户
 * 内存消耗：48.1 MB, 在所有 Java 提交中击败了49.44%的用户
 */
class Solution2 {

    public int[] smallestK(int[] arr, int k) {

        if (k == 0) return new int[0];
        quick_sort(arr, 0, arr.length - 1, k - 1);
        return Arrays.copyOf(arr, k);
    }

    private void quick_sort(int[] q, int l, int r, int k) {

        if (l >= r) return;

        int x = q[l + r + 1 >> 1], i = l - 1, j = r + 1;
        while (i < j) {
            do i++; while (q[i] < x);
            do j--; while (q[j] > x);
            if (i < j) swap(q, i, j);
        }

        if (k <= i - 1) quick_sort(q, l, i - 1, k);
        else quick_sort(q, i, r, k);
    }

    private void swap(int[] arr, int i, int j) {

        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    public static void main(String[] args) {

        int[] arr = {0, 1, 2, 1};
        System.out.println(Arrays.toString((new Solution2()).smallestK(arr, 1)));
    }
}

